A linklist is a common manner for organizing ordered data. It connects a series of data nodes as one data chain by a point and is an important way for realizing a linear list. A large number of linklist structures, which include apparatus lists and data organizations in various functional modules, are used in the core of Linux to organize data.
Apparently, the linklist is of better dynamism and capable of allocating spaces randomly. Knowledge of total amount of data is not needed in advance when the linklist is built. It is also possible to insert data in or delete data from any position in the linklist efficiently. An ordering property of the linklist causes traversal to be the operation most commonly used for the linklist. There are only two kinds of data that a traversal operation accesses frequently: node identifications and node pointers (only “next” pointer is used in a one-way linklist, while both “next” pointer and “pre” pointer are used in a two-way linklist).
The node identifications or the node pointers occupy a little memory; however, the identifications or the pointers of different nodes in the linklist are rarely located in the same line of the same physical page, wherein the same line means a segment of data, the length of which equals to that of a cache line inside a processor and which is aligned in the physical page. For example, assuming that the length of the cache line is 16 bytes, a memory is then divided into multiple segments, each being aligned data, with addresses whose last 4 bits are all 0. The data with addresses of 0x19ded0-0x19dedF is an aligned segment of data. The line in which certain data accessed by the processor locates will be loaded into the cache when this certain data is not in the cache, thus avoiding acquiring data from the memory every time.
During implementation of the present invention, the inventor analyzed features of the linklist carefully and found that the following problems exist in the related art.
The ordering property of accessing of the linklist and the discreteness of the linklist structure make it difficult for the linklist to be run on the processor efficiently. Since the identifications or the pointers of different nodes in the linklist are rarely located in the same line of the same physical page, data updating for a certain cache line may be triggered each time one node is traversed, so that not only the cache cannot be utilized in the traversal operation effectively, but also data of other applications In the data cache is likely to be eliminated, thus the performance of the entire system is affected.